home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graph / subgraph.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  975 b   |  64 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3.  
  4.  
  5. GRAPH<int,int> shortest_path_tree(GRAPH<int,int>& G, edge_array<int>& cost)
  6. {
  7.   // returns a shortest-paths tree  as a subgraph of G
  8.  
  9.   node_array<int> dist(G);
  10.   node_array<edge> pred(G);
  11.  
  12.   node s = G.first_node();
  13.  
  14.   DIJKSTRA(G,s,cost,dist,pred);
  15.  
  16.   list<edge> el;
  17.  
  18.   node v;
  19.   forall_nodes(v,G) if (pred[v]!=0) el.append(pred[v]);
  20.  
  21.   return GRAPH<int,int>(G,G.all_nodes(),el);   // subgraph constructor
  22. }
  23.  
  24.  
  25.  
  26. main()
  27.  
  28. { GRAPH<int,int> G;
  29.  
  30.   test_graph(G);
  31.  
  32.   edge_array<int> cost(G);
  33.  
  34.   int a = read_int("a = ");
  35.   int b = read_int("b = ");
  36.  
  37.   init_random();
  38.  
  39.   edge e;
  40.   forall_edges(e,G) cost[e] = G[e] = random(a,b);
  41.  
  42.  
  43.   GRAPH<int,int> S = shortest_path_tree(G,cost);
  44.  
  45.  
  46.   G.print("graph G");
  47.   newline; 
  48.  
  49.   S.print("subgraph S");
  50.   newline; 
  51.  
  52.  
  53.   edge_array<int> cost1(S);
  54.  
  55.   forall_edges(e,S) cost1[e] = S[e];  
  56.  
  57.   GRAPH<int,int> S1 = shortest_path_tree(S,cost1);
  58.  
  59.   S1.print("subgraph S1");
  60.   newline;
  61.  
  62. return 0;
  63. }
  64.